import math

class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l = len(nums)

        if l == 0 or nums[0] > target:
            return 0
        if nums[l - 1] < target:
            return l

        low = 0
        high = l - 1
        mid = math.floor((low + high) / 2)

        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            return self.searchInsert(nums[0:mid], target)
        else:
            return mid + 1 + self.searchInsert(nums[mid + 1:], target)


s = Solution()
print(s.searchInsert([1, 3], 2))
print(s.searchInsert([1, 3, 5, 6], 5))
print(s.searchInsert([1, 3, 5, 6], 2))
print(s.searchInsert([1, 3, 5, 6], 7))
print(s.searchInsert([1, 3, 5, 6], 0))
